2016-CVPR-Multi-label Ranking from Positive and Unlabeled Data

元論文のリンク

Introduction

multi labelのlearningにもPU使えますよね？あるデータ $\mathbf{x}$ に対して、複数の属性がある(タグ付けみたいに)時がmulti label learning。

この論文の問題設定は以下の3つ。

サンプル $\mathbf{x}$ にたいして、絶対にpositiveであるラベルがある。
サンプル $\mathbf{x}$ に対して、そのラベルは付けされいないが、絶対に含まれないというわけではないラベルがもう1つ。
サンプル $\mathbf{x}$ は複数個のラベルが付きうる。

これをPUに帰着するとき、multi label PU ranking問題にしている。

label rankingベースの研究がメイン。これはすべてのpositive例をnegative例の上に順位付けするという問題設定で、損失はRank Lossなるものであり先行研究でも提案されている。WSABIEとか。

Multi-label Ranking

問題設定。

$\mathcal{X}$ はサンプル空間であり、 $\mathbf{x}$ はサンプル。
ラベルは合計で $m$ 種類あり、 $\mathcal{Y} = \lbrace 0, 1 \rbrace ^ m$ である。1は付いていて、0は付いてない。
与えられたデータセットは $S = \lbrace (\mathbf{x} _i, y _i) \rbrace _{i = 1} ^ N$ である。
訓練する識別器は $\mathbf{f}(\mathbf{x}) = (f _1(\mathbf{x}), \cdots, f _m(\mathbf{x})) ^ T$ である。各ラベルについてつくかつかないかを予測する。
目標としては、以下のように、損失を最小限に抑えること。

\argmin _{\mathbf{f}} L(\mathbf{f}) = \mathbb{E} _{\mathbf{x}, \mathbf{y}} [L(f(\mathbf{x}), \mathbf{y})]

そして、ここではRank Lossを使う。

Rank Loss

L _{rank}(\mathbf{f}(\mathbf{x}), \mathbf{y}) = \sum _{i, j : y _i = 1, y _j = 0} [[f _i(\mathbf{x}) < f _j(\mathbf{x})]] + \frac{1}{2} [[f _i(\mathbf{x}) = f _j(\mathbf{x})]]

$[[ \cdot ]]$ 演算は指示関数で、条件を満たすならば1となる。

Ranking関数について、今回は0と1の二値しかないので上のような形になっている。すべての大小関係がはっきりしているペアについて、順序がひっくり返っているならペナルティ1、同じ順序なら0.5のペナルティを足すかたち。

これを用いて式変形すると、

\argmin _{\mathbf{f}} L(\mathbf{f}) = \mathbb{E} _{\mathbf{x}, \mathbf{y}} [L(f(\mathbf{x}), \mathbf{y})]\\ = \sum _{\mathbf{y} \in \mathcal{Y}} p(\mathbf{Y}) \mathbb{E} _{\mathbf{x} | \mathbf{y}} [L _{rank}(\mathbf{f}(\mathbf{x}), \mathbf{y})] \\ =\sum _{\mathbf{y} \in \mathcal{Y}} p(\mathbf{Y}) \sum _{i, j : y _i = 1, y _j = 0} \mathbb{E} _{\mathbf{x} | \mathbf{y}} [ [[f _i(\mathbf{x}) < f _j(\mathbf{x})]] + \frac{1}{2} [[f _i(\mathbf{x}) = f _j(\mathbf{x})]]]

この期待値の部分はmiss rank rateというものであり、以下のように書き直すこともできる。

R(\mathbf{x}, i, j) = \mathbb{E} _{\mathbf{x} | \mathbf{y}} [ [[f _i(\mathbf{x}) < f _j(\mathbf{x})]] + \frac{1}{2} [[f _i(\mathbf{x}) = f _j(\mathbf{x})]]] \\ = \mathbb{E} _{\mathbf{x} | y _i = 1, y _j = 0} [ [[f _i(\mathbf{x}) < f _j(\mathbf{x})]] + \frac{1}{2} [[f _i(\mathbf{x}) = f _j(\mathbf{x})]]] \\ = p(f_i(\mathbf{x}) < f_j(\mathbf{x}) | y _i = 1, y_j=0) + \frac{1}{2} p(f_i(\mathbf{x}) = f_j(\mathbf{x}) | y _i = 1, y_j=0)

これを使って書き直せば、以下のように損失関数になる。

L _{rank}(\mathbf{x}, \mathbf{y}) = \sum _{i, j : y _i = 1, y _j = 0} p(y_i=1, y_j=0) R(\mathbf{x}, i,j) \\ = \sum _{1 \leq i < j \leq m } p(y_i=1,y_j=0) R(\mathbf{x}, i,j) + p(y_i=0,y_j=1)p(\mathbf{x}, j,i)

i<jという条件を付けてループを回せば、このように「iは正しくjは違う確率」と「iは違いjは正しい確率」の和を考えている不整合を2つ分加算すればよく、計算が楽にできる。

この研究のシナリオはCase-Control。

Multi-label PU ranking

前述のように、multi-label PU rankingは以下の2つのラベルの状況から学習するものであった。

サンプル $\mathbf{x}$ にたいして、明確にラベルが割り当てられている場合、それはPositiveと見なせる。
ラベルが割り当てられてない場合、必ずNegativeではないとは限らない。Unlabeledとみなせる。

cost sensitiveなPU Learningへの帰着

上の式に $c_{ij}, c_{ji}$ という、クラスiがクラスjに誤分類された時のペナルティの重みを付ける。論文

例によって、 $R(\mathbf{x}, i,j)$ も $p(y_i=1,y_j=0)$ なども、Negativeデータがないので計算できない。これをPUで計算するために以下のような新たな誤分類率？ $R _X(\mathbf{x},i,j)$ を定義する。

R _X(\mathbf{x}, i,j) = p(f_i(\mathbf{x}) < f_j(\mathbf{x}) | s _i =1, s_j=0) + \frac{1}{2}p(f_i(\mathbf{x})=f_j(\mathbf{x})|s_i=1,s_j=0)

ラベルがついているか、ついていないかの $s$ で判断する。ここでの $s$ はPN分類で与えられたラベル $y$ の代わりであるPUのラベル。

これを不適切そうだが、割り切って使うとして、損失関数を新たに書き換えてみると以下のようになる。

\hat{L} _{rank} (\mathbf{x}) = \sum _{1 \leq i,j \leq m} p(s_i=1,s_j=0)R_X(\mathbf{x},i,j) + p(s_i=0,s_j=1)R_X(\mathbf{x},j,i)

仮定はSCAR、Select Completely At Randomで選択される。つまり、 $p(y_i = 1 | s_i = 0) = p(y_i = 1)$ である(選ばれるかどうかと関係なしにラベルがつく確率は同じ)

そして、 $p(\mathbf{x} | s_i = 1) = p(\mathbf{x} | y_i = 1)$ 、PUの時のラベル付きは、PNの時のPositiveサンプルと同じような分布が得られるというのもSCAR仮定からわかる。

2014 du Plessisらの書き換えと同様に、 $R_X$ は以下のように書き換えできる。

\pi _{j|i} = p(y_j=1|y_i=1) \\ R _{-X}(\mathbf{x},i,j)=p(f_i(\mathbf{x}) < f_j(\mathbf{x}) | y_i=1,y_j=1) + \frac{1}{2} p(f_i(\mathbf{x}) = f_j(\mathbf{x}) | y_i=1,y_j=1) \\

$\pi_{j|i}$ はi番目の属性がPositiveであるときの、j番目もPositiveである確率。
$R_{-X}$ は、足していく値は $R_X$ と同じだが、 $y_i=1,y_j=1$ という前提条件としている。
- $R_X$ は $y$ ではなく $s$ が条件であったし、そのうえ $s_i = 1, s_j = 0$ という条件であった。
$y_i=1$ という条件付きの下で、 $y_j$ について全パターンを集めて、 $\pi _{j|i} = p(y _j=1| y _i=1)$ の割合でそれぞれ配分している。

このように、 $R_X, R_{-X}$ を定義されたら以下のように、📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data, 📄2015-ICML-[uPU] Convex Formulation for Learning from Positive and Unlabeled Data で提案された $R_X$ の分解をすることができる。

R_X(\mathbf{x},i,j)=(1-\pi _{j|i})R(\mathbf{x},i,j)+\pi_{j|i} R_{-X}(\mathbf{x},i,j)

2014で提案していた $R_X$ の構成を、 $y_i=1$ という前提条件の下でやってみたというかたち。

$\pi _{j | i}$ の割合の $y_i = 1 | y_j = 1$ の条件の下での損失
$1 - \pi$ 割合の $y_i = 0 | y _j = 1$ の条件の下での損失

つまり、 $R_X$ というPUで使わないといけない損失は、上のようにPNで計算できる形に分解できる。これをうまく使って、PNの式出てて来る右辺を左辺で置き換えたい。

次のように $R(\mathbf{x},i,j)$ について上の式を解くと、以下のが得られる。を式変形できる。

R(\mathbf{x},i,j)=\frac{1}{1-\pi_{j|i}} (R_X(\mathbf{x},i,j)-\pi_{j|i}R_{-X}(\mathbf{x},i,j)) \\

これを用いて、集計を行うと以下のようになる。 $R_{-X}(\mathbf{x},i,j)+R_{-X}(\mathbf{x},j,i)=1$ を使う。

結果として、以下の

L _{rank}(\mathbf{x}) = \sum _{1 \leq i, j \leq m} \{ p(y_i=1) R_X(\mathbf{x},i,j)+ \\ p(y_j=1)R_X(\mathbf{x},j,i)-p(y_i=1,y_j=1) \}

が目標関数として得られる。 $p(y_i=1)$ のClass Priorは事前に得られる。 $p(y_i = 1, y_j = 1)$ は各クラス間に依存関係がないなら、単純に確率の積で求まるし、あってもLabeledされたデータから推定すればいい。

対称的な損失関数

L _{rank}(\mathbf{x}, \mathbf{y}) = \sum _{i, j : y _i = 1, y _j = 0} p(y_i=1, y_j=0) R(i,j) \\ = \sum _{1 \leq i < j \leq m } p(y_i=1,y_j=0) R(i,j) + p(y_i=0,y_j=1)R(j,i)

この式を $R_X$ に書き換えることによって、以下の形となる。

01損失では最適化できないので、代理損失を使うことを考える。

📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data で提案していた $l(x) + l(-x)=1$ となる対称な損失関数を、ここでも使うことができる。

ここでは、2014 du Plessisの提案にあるように、ランプ損失を使う。多クラス分類版としては、以下のものとなっている。多クラスの分類器の引いた差をRamp損失にそのまま突っ込んでいる。

グラフにしてみると以下のような形

Experiments

使用したデータセットは以下の3つ。

合成したもの
MSCOCO
NUS-WIDE

具体的な内容はここをみる。

Settings

ground truthがpositiveのラベルの欠損率を0から80%までで試した。

実験自体は、Single-Training-Set、Select Completely At Randomの設定で行っている。Case-Controlでもできるのでは…?

割合から乗算して欠損数を得る。
各クラスごとに何個欠けるのかについて、多項分布に従った1つのパターンをランダムに選ぶ。
各クラスで何個欠損するのかが決まったので、あとはSCARで選ぶ。

識別器の実装は

\mathbf{f}(\mathbf{x}) = W ^ T \mathbf{x}

とこのように多次元SVMであり、optimizationは無印の勾配降下法でやった。

多次元SVMの説明はこちら: 📄NNDL 第3章線形学習

この上で、L2正則化も行った。

Synthetic Dataset

各データについて、 $n$ 個のラベルが付くとして、これをポアソン分布から得る。
$n$ 個のラベルについてそれぞれ、クラス $c$ を選ぶ確率自体を、多項分布に従い選ぶ。
そのデータについて、特徴のサンプル回数 $k$ 自体もポアソン分布から得る。
1. 特徴のサンプル回数は、各クラスがそれぞれ特徴を持つとして、それの表現をサンプリング？
$k$ 回のサンプリングをそれぞれ行い、その得た特徴の和をサンプルとしている。

2000のテスト、8000の訓練データ。

実験結果として、全体のクラス数が2と少ないなら、ラベル付きが多ければ多いほど、手法がいい性能を持つが情報が減ると下がる。ただし8まで増えてしまうとなれば性能が低くなる。 全データでののべラベル数/クラス数の割合が性能の重要な鍵だとわかった。

Image Annotation Dataset

画像のデータセット2つ日してベンチマークを行った。訓練済み7層のAlexNetを使った。

Discussion

使用した損失関数と理想的な01損失の損失関数によるRiskの差は、

$p(s=0|y=1)$ の項目
ラベルのペア内の両方のラベルが割り当てられる確率(原文ままこれなに？)に比例する。

また、SCARの設定で問題を解いたので、Case Controlに適用させるとやはり、欠損率が低くても性能が低下する。

提案手法はラベルの欠損率が2割以上の時に有用である。

また、ラベルの存在自体にバイアスがあるとき、例えば犬、猫、人間は高確率で一緒に存在するならば、「猫、人間」、「犬、猫、人間」とラベル付けされたデータは似た特徴を持つかもしれない(というかそもそも同じかもしれない)このようなデータの分離はさすがにこの手法では無理。

クラス事前確率の $\pi=p(y=+1)$ は雑に推定したが実用上はもっと丁寧に推定するべきだな。